﻿


//博客： 动态规划-回文串问题所用案例代码，博客链接如下：
//https://blog.csdn.net/weixin_64099089/article/details/147634638?sharetype=blogdetail&sharerId=147634638&sharerefer=PC&sharesource=weixin_64099089&spm=1011.2480.3001.8118


//https://leetcode.cn/problems/palindromic-substrings/

//647. 回文子串
//
//给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
//
//回文字符串 是正着读和倒过来读一样的字符串。
//
//子字符串 是字符串中的由连续字符组成的一个序列。
//
//示例 1：
//输入：s = "abc"
//输出：3
//解释：三个回文子串 : "a", "b", "c"
//示例 2：
//
//输入：s = "aaa"
//输出：6
//解释：6个回文子串 : "a", "a", "a", "aa", "aa", "aaa"
//
//提示：
//
//1 <= s.length <= 1000
//s 由小写英文字母组成
//

//中心扩展法
class Solution {
public:
    int countSubstrings(string s) {
        //中心扩展法
        int res = 0, n = s.size();
        for (int i = 0; i < n; ++i) {  //枚举每一个回文子串的中心点
            //1 以s[i]为中心，回文串的长度为奇数
            res++; //首先s[i] 本身是一个回文子串
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n) {
                if (s[left] == s[right]) res++;
                else break;
                --left, ++right; //尝试扩大区间，再将当前回文子串的左右两个字符加入进来，看是否还构成回文子串
            }
            //2 以s[i] 和 s[i+1]为中心，回文串的长度为偶数
            left = i, right = i + 1;
            while (left >= 0 && right < n) {
                if (s[left] == s[right]) res++;
                else break;
                --left, ++right;
            }
        }
        return res;
    }
};

//动态规划
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, true));
        int res = n;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
                if (dp[i][j]) ++res;
            }
        }
        return res;
    }
};


//https://leetcode.cn/problems/longest-palindromic-substring/
//5. 最长回文子串
//给你一个字符串 s，找到 s 中最长的 回文 子串。
//示例 1：
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//示例 2：
//
//输入：s = "cbbd"
//输出："bb"
//
//
//提示：
//
//1 <= s.length <= 1000
//s 仅由数字和英文字母组成

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, true));
        int res = 1, left = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
                if (dp[i][j]) {
                    if (j - i + 1 > res) {
                        res = j - i + 1;
                        left = i;
                    }
                }
            }
        }
        return s.substr(left, res);
    }
};


//https://leetcode.cn/problems/palindrome-partitioning/
//131. 分割回文串
//给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案
//
//示例 1：
//
//输入：s = "aab"
//输出： [["a", "a", "b"], ["aa", "b"]]
//示例 2：
//
//输入：s = "a"
//输出： [["a"]]
//
//
//    提示：
//
//        1 <= s.length <= 16
//        s 仅由小写英文字母组成

class Solution {
public:
    void Split(const string& s, const vector<vector<bool>>& dp, int start, vector<string> split, vector<vector<string>>& res) {
        //需要分割 [start,n-1] 的子串
        //如果start == n ，那么说明已经分割完了
        if (start == s.size()) res.push_back(move(split)); //说明已经拆分完了，同时拆分的结果保存在split中
        //判断start开始的所有子串中，是否有回文串，如果有，就尝试将其再次分割
        for (int i = start; i < s.size(); ++i) {
            if (dp[start][i]) {
                split.push_back(s.substr(start, i - start + 1));
                Split(s, dp, i + 1, split, res); //下一轮分割从 i+1 开始
                //判断完之后回退
                split.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
            }
        }
        //预处理完之后，开始分割
        //返回s的所有的分割方案，我们可以拆分成子问题
        //首先在 s 的前半部分找出一个回文串，将其拆分出来，然后再对剩余部分进行分割，而剩余部分的分割就是子问题
        //设计为回溯
        vector<vector<string>> res;
        vector<string> split; //用于保存当前栈帧的结果
        split.reserve(n);
        Split(s, dp, 0, split, res);  //分割的是 [0,n-1]的串
        return res;
    }
};



//https://leetcode.cn/problems/palindrome-partitioning-iv/
//1745. 分割回文串 IV
//给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
//
//当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
//
//示例 1：
//
//输入：s = "abcbdd"
//输出：true
//解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
//示例 2：
//
//输入：s = "bcbddxy"
//输出：false
//解释：s 没办法被分割成 3 个回文子字符串。
//
//
//提示：
//
//3 <= s.length <= 2000
//s​​​​​​ 只包含小写英文字母。


class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
            }
        }
        //枚举两个边界
        // [0,i],[i+1,j],[j+1,n-1]
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) return true;
            }
        }
        return false;
    }
};


//https://leetcode.cn/problems/palindrome-partitioning-ii/
//132. 分割回文串 II
//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
//
//返回符合要求的 最少分割次数 。
//
//示例 1：
//
//输入：s = "aab"
//输出：1
//解释：只需一次分割就可将 s 分割成["aa", "b"] 这样两个回文子串。
//示例 2：
//
//输入：s = "a"
//输出：0
//示例 3：
//
//输入：s = "ab"
//输出：1
//
//
//提示：
//
//1 <= s.length <= 2000
//s 仅由小写英文字母组成

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        //预处理枚举所有的子串是否为回文串
        vector<vector<bool>> is(n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                is[i][j] = s[i] == s[j] && is[i + 1][j - 1];
            }
        }
        vector<int>dp(n, 0x3fffffff); //dp[i] 表示将[0,i]拆分成回文串所需的最少分割次数
        dp[0] = 0;
        for (int i = 1; i < n; ++i) {
            if (!is[0][i]) { //[0,i]不是回文串的时候才需要分割
                for (int j = 1; j <= i; ++j) { //判断[j,i]是否回文，如果是，尝试将其分割
                    if (is[j][i]) {
                        dp[i] = min(dp[j - 1] + 1, dp[i]);
                    }
                }
            }
            else dp[i] = 0;  //不需要划分
        }
        return dp[n - 1];
    }
};


//https://leetcode.cn/problems/longest-palindromic-subsequence/

//516. 最长回文子序列
//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
//
//子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
//
//示例 1：
//
//输入：s = "bbbab"
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
//示例 2：
//
//输入：s = "cbbd"
//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
//
//
//提示：
//
//1 <= s.length <= 1000
//s 仅由小写英文字母组成

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>>dp(n, vector<int>(n));
        dp[0][0] = dp[n - 1][n - 1] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j) {
                    dp[i][j] = 1; //特殊处理
                    continue;
                }
                if (s[i] == s[j]) dp[i][j] = 2 + dp[i + 1][j - 1];  //注意，这里dp[i+1][j-1]有可能不合法，但是他们填的值是0，不影响结果
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};


//https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
//1312. 让字符串成为回文串的最少插入次数
//给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
//
//请你返回让 s 成为回文串的 最少操作次数 。
//
//「回文串」是正读和反读都相同的字符串。
//
//示例 1：
//
//输入：s = "zzazz"
//输出：0
//解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
//示例 2：
//
//输入：s = "mbadm"
//输出：2
//解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
//示例 3：
//
//输入：s = "leetcode"
//输出：5
//解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
//
//
//提示：
//
//1 <= s.length <= 500
//s 中所有字符都是小写字母。

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0x3fffffff));
        // dp[0][0] = dp[n-1][n-1] = 0;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (i == j) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i == j - 1) {
                    dp[i][j] = s[i] == s[j] ? 0 : 1;
                    continue;
                }
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
                else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[0][n - 1];
    }
};














